/**
 * $Id: FibonacciHeap.java,v 1.2 2009-11-24 12:00:28 gaudenz Exp $
 * Copyright (c) 2007, Gaudenz Alder
 */
package com.kg.rails.component.editor.analysis;

import java.util.Hashtable;
import java.util.Map;

/**
 * This class implements a priority queue.
 */
public class FibonacciHeap {

    /**
     * Maps from elements to nodes
     */
    protected Map<Object, Node> nodes = new Hashtable<Object, Node>();

    /**
     *
     */
    protected Node min;

    /**
     *
     */
    protected int size;

    /**
     * Returns the node that represents element.
     */
    public Node getNode(Object element, boolean create) {
        Node node = nodes.get(element);

        if (node == null && create) {
            node = new Node(element, Double.MAX_VALUE);
            nodes.put(element, node);
            insert(node, node.getKey());
        }
        return node;
    }

    /**
     * Returns true if the queue is empty.
     */
    public boolean isEmpty() {
        return min == null;
    }

    /**
     * Decreases the key value for a heap node, given the new value to take on.
     * The structure of the heap may be changed and will not be consolidated.
     * <p/>
     * <p>
     * Running time: O(1) amortized
     * </p>
     *
     * @param x Node whose value should be decreased.
     * @param k New key value for node x.
     * @throws IllegalArgumentException Thrown if k is larger than x.key value.
     */
    public void decreaseKey(Node x, double k) {
        if (k > x.key) {
            throw new IllegalArgumentException(
                    "decreaseKey() got larger key value");
        }

        x.key = k;
        Node y = x.parent;

        if ((y != null) && (x.key < y.key)) {
            cut(x, y);
            cascadingCut(y);
        }

        if (min == null || x.key < min.key) {
            min = x;
        }
    }

    /**
     * Deletes a node from the heap given the reference to the node. The trees
     * in the heap will be consolidated, if necessary. This operation may fail
     * to remove the correct element if there are nodes with key value
     * -Infinity.
     * <p/>
     * <p>
     * Running time: O(log n) amortized
     * </p>
     *
     * @param x The node to remove from the heap.
     */
    public void delete(Node x) {
        // make x as small as possible
        decreaseKey(x, Double.NEGATIVE_INFINITY);

        // remove the smallest, which decreases n also
        removeMin();
    }

    /**
     * Inserts a new data element into the heap. No heap consolidation is
     * performed at this time, the new node is simply inserted into the root
     * list of this heap.
     * <p/>
     * <p>
     * Running time: O(1) actual
     * </p>
     *
     * @param node new node to insert into heap
     * @param key  key value associated with data object
     */
    public void insert(Node node, double key) {
        node.key = key;

        // concatenate node into min list
        if (min != null) {
            node.left = min;
            node.right = min.right;
            min.right = node;
            node.right.left = node;

            if (key < min.key) {
                min = node;
            }
        } else {
            min = node;
        }

        size++;
    }

    /**
     * Returns the smallest element in the heap. This smallest element is the
     * one with the minimum key value.
     * <p/>
     * <p>
     * Running time: O(1) actual
     * </p>
     *
     * @return Returns the heap node with the smallest key.
     */
    public Node min() {
        return min;
    }

    /**
     * Removes the smallest element from the heap. This will cause the trees in
     * the heap to be consolidated, if necessary.
     * Does not remove the data node so that the current key remains stored.
     * <p/>
     * <p>
     * Running time: O(log n) amortized
     * </p>
     *
     * @return Returns the node with the smallest key.
     */
    public Node removeMin() {
        Node z = min;

        if (z != null) {
            int numKids = z.degree;
            Node x = z.child;
            Node tempRight;

            // for each child of z do...
            while (numKids > 0) {
                tempRight = x.right;

                // remove x from child list
                x.left.right = x.right;
                x.right.left = x.left;

                // add x to root list of heap
                x.left = min;
                x.right = min.right;
                min.right = x;
                x.right.left = x;

                // set parent[x] to null
                x.parent = null;
                x = tempRight;
                numKids--;
            }

            // remove z from root list of heap
            z.left.right = z.right;
            z.right.left = z.left;

            if (z == z.right) {
                min = null;
            } else {
                min = z.right;
                consolidate();
            }

            // decrement size of heap
            size--;
        }

        return z;
    }

    /**
     * Returns the size of the heap which is measured in the number of elements
     * contained in the heap.
     * <p/>
     * <p>
     * Running time: O(1) actual
     * </p>
     *
     * @return Returns the number of elements in the heap.
     */
    public int size() {
        return size;
    }

    /**
     * Joins two Fibonacci heaps into a new one. No heap consolidation is
     * performed at this time. The two root lists are simply joined together.
     * <p/>
     * <p>
     * Running time: O(1) actual
     * </p>
     *
     * @param h1 The first heap.
     * @param h2 The second heap.
     * @return Returns a new heap containing h1 and h2.
     */
    public static FibonacciHeap union(FibonacciHeap h1, FibonacciHeap h2) {
        FibonacciHeap h = new FibonacciHeap();

        if ((h1 != null) && (h2 != null)) {
            h.min = h1.min;

            if (h.min != null) {
                if (h2.min != null) {
                    h.min.right.left = h2.min.left;
                    h2.min.left.right = h.min.right;
                    h.min.right = h2.min;
                    h2.min.left = h.min;

                    if (h2.min.key < h1.min.key) {
                        h.min = h2.min;
                    }
                }
            } else {
                h.min = h2.min;
            }

            h.size = h1.size + h2.size;
        }

        return h;
    }

    /**
     * Performs a cascading cut operation. This cuts y from its parent and then
     * does the same for its parent, and so on up the tree.
     * <p/>
     * <p>
     * Running time: O(log n); O(1) excluding the recursion
     * </p>
     *
     * @param y The node to perform cascading cut on.
     */
    protected void cascadingCut(Node y) {
        Node z = y.parent;

        // if there's a parent...
        if (z != null) {
            // if y is unmarked, set it marked
            if (!y.mark) {
                y.mark = true;
            } else {
                // it's marked, cut it from parent
                cut(y, z);

                // cut its parent as well
                cascadingCut(z);
            }
        }
    }

    /**
     * Consolidates the trees in the heap by joining trees of equal degree until
     * there are no more trees of equal degree in the root list.
     * <p/>
     * <p>
     * Running time: O(log n) amortized
     * </p>
     */
    protected void consolidate() {
        int arraySize = size + 1;
        Node[] array = new Node[arraySize];

        // Initialize degree array
        for (int i = 0; i < arraySize; i++) {
            array[i] = null;
        }

        // Find the number of root nodes.
        int numRoots = 0;
        Node x = min;

        if (x != null) {
            numRoots++;
            x = x.right;

            while (x != min) {
                numRoots++;
                x = x.right;
            }
        }

        // For each node in root list do...
        while (numRoots > 0) {
            // Access this node's degree..
            int d = x.degree;
            Node next = x.right;

            // ..and see if there's another of the same degree.
            while (array[d] != null) {
                // There is, make one of the nodes a child of the other.
                Node y = array[d];

                // Do this based on the key value.
                if (x.key > y.key) {
                    Node temp = y;
                    y = x;
                    x = temp;
                }

                // Node y disappears from root list.
                link(y, x);

                // We've handled this degree, go to next one.
                array[d] = null;
                d++;
            }

            // Save this node for later when we might encounter another
            // of the same degree.
            array[d] = x;

            // Move forward through list.
            x = next;
            numRoots--;
        }

        // Set min to null (effectively losing the root list) and
        // reconstruct the root list from the array entries in array[].
        min = null;

        for (int i = 0; i < arraySize; i++) {
            if (array[i] != null) {
                // We've got a live one, add it to root list.
                if (min != null) {
                    // First remove node from root list.
                    array[i].left.right = array[i].right;
                    array[i].right.left = array[i].left;

                    // Now add to root list, again.
                    array[i].left = min;
                    array[i].right = min.right;
                    min.right = array[i];
                    array[i].right.left = array[i];

                    // Check if this is a new min.
                    if (array[i].key < min.key) {
                        min = array[i];
                    }
                } else {
                    min = array[i];
                }
            }
        }
    }

    /**
     * The reverse of the link operation: removes x from the child list of y.
     * This method assumes that min is non-null.
     * <p/>
     * <p>
     * Running time: O(1)
     * </p>
     *
     * @param x The child of y to be removed from y's child list.
     * @param y The parent of x about to lose a child.
     */
    protected void cut(Node x, Node y) {
        // remove x from childlist of y and decrement degree[y]
        x.left.right = x.right;
        x.right.left = x.left;
        y.degree--;

        // reset y.child if necessary
        if (y.child == x) {
            y.child = x.right;
        }

        if (y.degree == 0) {
            y.child = null;
        }

        // add x to root list of heap
        x.left = min;
        x.right = min.right;
        min.right = x;
        x.right.left = x;

        // set parent[x] to nil
        x.parent = null;

        // set mark[x] to false
        x.mark = false;
    }

    /**
     * Make node y a child of node x.
     * <p/>
     * <p>
     * Running time: O(1) actual
     * </p>
     *
     * @param y The node to become child.
     * @param x The node to become parent.
     */
    protected void link(Node y, Node x) {
        // remove y from root list of heap
        y.left.right = y.right;
        y.right.left = y.left;

        // make y a child of x
        y.parent = x;

        if (x.child == null) {
            x.child = y;
            y.right = y;
            y.left = y;
        } else {
            y.left = x.child;
            y.right = x.child.right;
            x.child.right = y;
            y.right.left = y;
        }

        // increase degree[x]
        x.degree++;

        // set mark[y] false
        y.mark = false;
    }

    /**
     * Implements a node of the Fibonacci heap. It holds the information
     * necessary for maintaining the structure of the heap. It also holds the
     * reference to the key value (which is used to determine the heap
     * structure). Additional Node data should be stored in a subclass.
     */
    public static class Node {

        Object userObject;

        /**
         * first child node
         */
        Node child;

        /**
         * left sibling node
         */
        Node left;

        /**
         * parent node
         */
        Node parent;

        /**
         * right sibling node
         */
        Node right;

        /**
         * true if this node has had a child removed since this node was added
         * to its parent
         */
        boolean mark;

        /**
         * key value for this node
         */
        double key;

        /**
         * number of children of this node (does not count grandchildren)
         */
        int degree;

        /**
         * Default constructor. Initializes the right and left pointers, making
         * this a circular doubly-linked list.
         *
         * @param key The initial key for node.
         */
        public Node(Object userObject, double key) {
            this.userObject = userObject;
            right = this;
            left = this;
            this.key = key;
        }

        /**
         * Obtain the key for this node.
         *
         * @return the key
         */
        public final double getKey() {
            return key;
        }

        /**
         * @return Returns the userObject.
         */
        public Object getUserObject() {
            return userObject;
        }

        /**
         * @param userObject The userObject to set.
         */
        public void setUserObject(Object userObject) {
            this.userObject = userObject;
        }

    }

}